import java.util.ArrayList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=500 lang=java
 *
 * [500] 键盘行
 *
 * https://leetcode-cn.com/problems/keyboard-row/description/
 *
 * algorithms
 * Easy (64.64%)
 * Total Accepted:    5.4K
 * Total Submissions: 8.3K
 * Testcase Example:  '["Hello","Alaska","Dad","Peace"]'
 *
 * 给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 示例：
 * 
 * 输入: ["Hello", "Alaska", "Dad", "Peace"]
 * 输出: ["Alaska", "Dad"]
 * 
 * 
 * 
 * 
 * 注意：
 * 
 * 
 * 你可以重复使用键盘上同一字符。
 * 你可以假设输入的字符串将只包含字母。
 * 
 */
class Solution {

    private static final int[] CHAR_TO_LINE = new int[26];

    static {
        String[] lines = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
        for (int i=0; i<lines.length; ++i) {
            String line = lines[i];
            for (int j=0; j<line.length(); ++j) {
                CHAR_TO_LINE[line.charAt(j) - 'a'] = i;
            }
        }
    }

    public String[] findWords(String[] words) {
        List<String> ans = new ArrayList<>(words.length);
        for (String word : words) {
            if (word.length() == 0) {
                ans.add(word);
                continue;
            }
            String lowerWord = word.toLowerCase();
            int line = CHAR_TO_LINE[lowerWord.charAt(0) - 'a'];
            boolean ok = true;
            for (int i=1; i<lowerWord.length(); ++i) {
                int t = CHAR_TO_LINE[lowerWord.charAt(i) - 'a'];
                if (t != line) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                ans.add(word);
            }
        }
        String[] arr = new String[ans.size()];
        ans.toArray(arr);
        return arr;
    }
}

